//**		PLEASE READ!		**//
//**		PLEASE READ!		**//
//This List requires you to delete your own memory. It is only a holder.  If you pass a variable or a pointer
// into it, the List will hold onto it until a remove function is called to remove it.  The remove function returns a -Record- struct
// This struct holds a string with the data type that was passed in when the object was added. The data in the -Record- is held in a void * and
// the -Record- does not contain a deconstructor that is able to delete it.
//Let Brandon York know if there are any bugs or addition features that need to be addressed.
//**		PLEASE READ!		**//
//**		PLEASE READ!		**//
#pragma once
#ifndef NULL
#define NULL 0
#endif

//This is the "Node" used by the linked list
//Anything can be stored in a Record, but it will not be deleted by it, !EVER!
// The cstring is for debugging purposes only. It provides no functionality
struct Record
{
	char * Type;
	void * Data;
	Record * Next;
	Record * Prev;
	Record():Data(NULL),Next(NULL),Prev(NULL) {}
	Record(void * Data):Data(Data),Next(NULL),Prev(NULL) {}
	Record(char * Type,void * Data):Data(Data),Type(Type),Next(NULL),Prev(NULL) {}	
	~Record() {
		
		Data = NULL;
		if(Type)
		delete [] Type;
		Next = NULL;
		Prev = NULL;
	}
};


/**
  *This List has a linked list with a pointer to each node in the m_IDs array. They are stored as integers and are typecasted to get the pointer.
  *The reason there is both an array and a linked list is complex.  To begin with, the Linked list allows the data to stay in one location and not have to worry about
  *moving around. The array provides easy and quick access to any point in the linked list.  Bringing both aspects together, security and speed. It
  *makes up for this in have to hold onto a little extra memory.  
  *
  * !Code Examples!
  *ILL Test;
  *Record * R;
  *
  *Bad Example
  *A basic test of non pointer values being stored and printed out.
  *<code>
  *int i = 0;
  *int i2 = 2;
  *Test.Add("Int",(void*)&i);
  *Test.Add("Int2",(void*)&i2);
  *float f = 1;
  *Test.Add("Float",(void*)&f);
  *printf("%s\n",Test.Get(0)->Type);
  *R = Test.Remove_by_Value((void*)&i2);
  *printf("%f",*((float*)(Test.Get(0)->Data)));
  *</code>
  *This is dangerous using anything that is over or under 4 bytes.
  * You cannot delete a non pointer variable and the Record pointer does not
  * delete its data. It only sets it to NULL. That data will be picked up
  * by the microsoft garbage collecter, but its not something to be counted on.
  *
  *Good Example
  *A basic test of pointer values being stored and printed out
  *<code>
  *int * i = new int();*i = 0;
  *int * i2 = new int();*i2 = 2;
  *Test.Add("Int",(void*)i);
  *Test.Add("Int2",(void*)i2);
  *float * f = new float();*f = 1;
  *Test.Add("Float",(void*)f);
  *R = Test.Remove_by_Value((void*)i2);
  *i2 = (int*) R->Data;
  *delete i2;
  *printf("%s\n",Test.Get(1)->Type);
  *printf("%f",*((float*)(Test.Get(1)->Data)));
  *</code>
  *This example is how the IndexedLinkedList should be used.  Although it still does not
  *delete your memory for you. You can still delete it yourself.
  *Some example Code
  *
  *
  */
class IndexedLinkedList
{
private:
	Record * Head;
	Record * Last;
	int m_Size;
	int m_Allocated;
	int * m_IDs;

	//For use by the class only
	void Ensure_Capacity(int a_Size) {
		int * new_IDs = NULL;
		if(a_Size <= m_Allocated-10) {
			new_IDs = new int[m_Allocated-=5];
		}
		else if (a_Size >= m_Allocated) {
			new_IDs = new int[m_Allocated+=5];
		}
		else return;
		for(int i = 0;i < m_Size;i++) {
			new_IDs[i] = m_IDs[i];
		}
		if(m_IDs) delete m_IDs;
		m_IDs = new_IDs;
	}

	void Add_ID(int a_ID) {
		Ensure_Capacity(m_Size+1);
		m_IDs[m_Size++] = a_ID;
	}

	void Insert_ID(int a_ID,int a_index) {
		Ensure_Capacity(m_Size+1);
		for(int i = a_index;i < m_Size;i++) {
			m_IDs[i+1] = m_IDs[i];
		}
		m_IDs[a_index] = a_ID;
		m_Size++;
	}

	void Remove_ID(int a_index) {
		for(int i = a_index;i < m_Size;i++) {
			if(m_IDs[i]) {
				m_IDs[i] = m_IDs[i+1];
			}
		}
		m_IDs[--m_Size] = 0;
	}
	//

public:
	IndexedLinkedList() {
		m_Size = 0;
		m_Allocated = 5;
		Head = NULL;
		Last = NULL;
		m_IDs = new int[m_Allocated];
		for(int i = 0;i < m_Allocated;i++) {
			m_IDs[i] = 0;
		}
	}

	~IndexedLinkedList() {
		for(;Empty();) {
			Remove_Last();
		}
		if(Head) delete Head;
		if(Last) delete Last;
		if(m_IDs[0])delete [] m_IDs;
	}

	int GetSize() { return m_Size; }
	
	Record * Get(int i) 
	{ 
		return (Record*)m_IDs[i]; 
	}
	
	int IndexOf(void * a_Data) {
		for(int i = 0;i < m_Size;i++) {
			if(((Record*)m_IDs[i])->Data == a_Data) {
				return i;
			}
		}
		return -1;
	}
	
	bool Has(void * a_Data) {
		for(int i = 0;i < m_Size;i++) {
			if(((Record*)m_IDs[i])->Data == a_Data) {
				return true;
			}
		}
		return false;
	}

	bool Empty() {
		if(Head)
			return true;
		return false;
	}
	
	//Does not clean up data in list
	// It only clean up the list
	void Clear() {
		while(Head)
			Remove_Last();
	}
	
	void Add(char * a_Type, void * a_Data) {
		Record * New = new Record(a_Type,a_Data);
		if(!Head == NULL) {
			Last->Next = New;
			New->Prev = Last;
		}
		else {
			Head = New;
		}
		Last = New;
		Add_ID((int)New);
	}
	
	void Add2Head(char * a_Type,void * a_Data) {
		Record * New = new Record(a_Type,a_Data);
		if(Head == NULL) {
			Head = Last = New;
			Add_ID((int)New);
		}
		else {
			New->Next = Head;
			Head->Prev = New;
			Head = New;
			Insert_ID((int)New,0);
		}
	}
	
	void Insert(char * a_Type, void * a_Data, int a_index) {
		Record * N,* P,* New;
		New = new Record(a_Type,a_Data);
		for(int i = 0;i < m_Size;i++) {
			if(i == a_index) {
				if(((Record*)m_IDs[i])->Prev) {
					P = ((Record*)m_IDs[i])->Prev;
					if(((Record*)m_IDs[i])->Prev->Next) {
						N = ((Record*)m_IDs[i])->Prev->Next;
						P->Next = New;
						N->Prev = New;
						New->Prev = P;
						New->Next = N;
					}
					else {
						P->Next = New;
						New->Prev = P;
					}
					Insert_ID((int)New,a_index);
				}
				else  {
					Add2Head(a_Type,a_Data);
				}			
			}
		}
	}

	void Add_List(IndexedLinkedList * List) {
		for(int i = 0;i < List->GetSize();i++) {
			Add(List->Get(i)->Type,List->Get(i)->Data);
		}
	}

	Record * Remove_by_Value(void * a_Data) {
		Record * Temp = NULL;
		for(int i = 0;i < m_Size;i++) {
			if(((Record*)m_IDs[i])->Data == a_Data) {
				Temp = (Record*)m_IDs[i];
				if( Head == Temp ) {
					if( Head == Last ) {
						Head = Last = NULL;
					}
					else {
						Temp->Next->Prev = NULL;
						Head = Temp->Next;
					}
				}
				else if ( Last == Temp ) {
					Last = Temp->Prev;
					Temp->Prev->Next = NULL;
				}
				else {
					Temp->Prev->Next = Temp->Next;
					Temp->Next->Prev = Temp->Prev;
				}
				Remove_ID(i);
				return Temp;
			}
		}
		return NULL;
	}
	
	Record * Remove_Last() {
		Record * Temp = Last;
		if( Temp ) {
			if( Temp->Prev ) {
				Last = Temp->Prev;
				Last->Next = NULL;
			}
			else {
				Head = Last = NULL;
			}
			Remove_ID(m_Size);
			return Temp;
		}
		return NULL;
	}
	


	Record * Remove_First() {
		Record * Temp = Head;
		if( Temp ) {
			if( Temp->Next ) {
				Head = Temp->Next;
				Head->Prev = NULL;
			}
			else {
				Head = Last = NULL;
			}
			Remove_ID(0);
			return Temp;
		}
		return NULL;
	}

};
typedef IndexedLinkedList ILL;